package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-06 20:05
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 打家劫舍2 {

    public int rob(int[] nums) {
        int n = nums.length;
        int[] newNum = new int[n+1];
        if (nums.length == 1) return newNum[1];
        for (int i = 1; i <= n; i++) {
            newNum[i] = nums[i-1];
        }

        int[][] f = new int[n+1][2];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(f[i],-100000000);
        }


        /**
         *  选了1就不可以选n
         *  选了n就不可以选1
         *  两个都计算一下，判断大小
         */


        // 偷的是n
        f[1][0] = 0;
        f[1][1] = -10000000; // 第一天没有被偷

        // 从第二天开始计算
        for (int i = 2; i <= n; i++) {
            // 不偷
            f[i][0] = Math.max(f[i][0],Math.max(f[i-1][0],f[i-1][1]));
            // 偷
            f[i][1] = Math.max(f[i][1],f[i-1][0]+newNum[i]);
        }

        int ans2 = Math.max(f[n][0],f[n][1]);

        // 偷的是1
        f[1][0] = 0;
        f[1][1] = newNum[1]; // 第一天偷了

        // 从第二天开始计算
        for (int i = 2; i <= n; i++) {
            // 不偷
            f[i][0] = Math.max(f[i][0],Math.max(f[i-1][0],f[i-1][1]));
            // 偷
            f[i][1] = Math.max(f[i][1],f[i-1][0]+newNum[i]);
        }

        int ans1 = f[n][0];


        return Math.max(ans1,ans2);
    }

}
